import java.io.IOException;
import java.util.ArrayList;
import java.util.Iterator;

public class PRQuadFile {
	private enum Quadrant {
		NW, NE, SW, SE
	};

	/* Private Classes */

	/**
	 * abstract QuadNode base class
	 * 
	 */
	private abstract class prQuadNode {
		public abstract boolean isLeaf();

		public abstract int size();

		public abstract void printData();

		public abstract void saveNode();
		
		public Integer addr;
	}

	/**
	 * internal node implementation
	 * 
	 */
	private class prQuadInternal extends prQuadNode {
		private Integer NE, NW, SE, SW;
		private Integer addr;

		public prQuadInternal(Integer allocated) {
			addr = allocated;
			setNE(-1);
			setNW(-1);
			setSE(-1);
			setSW(-1);
		}

		public boolean isLeaf() {
			return false;
		}

		public Integer getNE() {
			return NE;
		}

		public void setNE(Integer nE) {
			NE = nE;
		}

		public Integer getNW() {
			return NW;
		}

		public void setNW(Integer nW) {
			NW = nW;
		}

		public Integer getSE() {
			return SE;
		}

		public void setSE(Integer sE) {
			SE = sE;
		}

		public Integer getSW() {
			return SW;
		}

		public void setSW(Integer sW) {
			SW = sW;
		}

		public int size() {
			int s = 0;
			if (NW != -1) s += getNode(NW).size();
			if (NE != -1) s += getNode(NE).size();
			if (SW != -1) s += getNode(SW).size();
			if (SE != -1) s += getNode(SE).size(); 
			return s;
		}

		public void printData() {
			System.out.print("(");
			if (NW == -1)
				System.out.print("*");
			else
				getNode(NW).printData();
			System.out.print("|");
			if (NE == -1)
				System.out.print("*");
			else
				getNode(NE).printData();
			System.out.print("|");
			if (SW == -1)
				System.out.print("*");
			else
				getNode(SW).printData();
			System.out.print("|");
			if (SE == -1)
				System.out.print("*");
			else
				getNode(SE).printData();
			System.out.print("|)");
			System.out.flush();
		}

		public void saveNode() {
			byte[] data = new byte[17];
			data[0] = INTERNAL;
			insertToByteArray(NW, 1, data);
			insertToByteArray(NE, 5, data);
			insertToByteArray(SW, 9, data);
			insertToByteArray(SE, 13, data);
			try {
				pool.write(addr, data, (byte) 17);
			} catch (IOException e) {
				System.err.println("IOException occurred during Node write.");
			}
		}
		
		private void readElements() {
			byte[] buff = new byte[17];
			try {
				pool.read(addr, buff);
			} catch (IOException e) {
				System.err.println("IOException while reading internal node.");
			}
			
			NW = getIntegerFromByteArray(buff, 1);
			NE = getIntegerFromByteArray(buff, 5);
			SW = getIntegerFromByteArray(buff, 9);
			SE = getIntegerFromByteArray(buff, 13);
		}
	}

	/**
	 * leaf node implementation
	 * 
	 */
	private class prQuadLeaf extends prQuadNode {
		public ArrayList<Integer> handles;
		private Integer addr;

		public prQuadLeaf(Integer handle) {
			addr = handle;
			handles = new ArrayList<Integer>();
		}

		public boolean insertCity(Integer cityHandle, City c) {
			if (handles.size() >= MAX_BUCKET_SIZE) {
				return false;
			} else {
				handles.add(cityHandle);
				byte[] buff = new byte[12];
				insertToByteArray(c.getCoordinates().getXCoord(), 0, buff);
				insertToByteArray(c.getCoordinates().getYCoord(), 4, buff);
				insertToByteArray(c.handle(), 8, buff);
				try {
					pool.write(cityHandle, buff, (byte) 12);
				} catch (IOException e) {
					System.err
							.println("IOExcpetion while writing city record to file.");
				}

				saveNode();
				return true;
			}
		}

		public boolean isLeaf() {
			return true;
		}

		public int size() {
			return handles.size();
		}

		public final void printData() {
			if (handles.size() == 0) {
				System.out.print("*");
				System.out.flush();
			} else {
				Iterator<Integer> iter = handles.iterator();
				while (iter.hasNext()) {
					City val = getCity(iter.next());
					System.out.print(val.toString() + ","
							+ readString(val.handle()) + ":");
				}
			}
		}

		public void saveNode() {
			byte[] arr = new byte[14];
			arr[0] = LEAF;
			arr[1] = (byte) handles.size();

			for (int i = 0; i < handles.size(); i++) {
				insertToByteArray(handles.get(i), 2 + (i * 4), arr);
			}

			try {
				pool.write(addr, arr, (byte) 14);
			} catch (IOException e) {
				System.err
						.println("IOException while attempting to write Leaf node");
			}
		}

		private void readElements() {
			handles = new ArrayList<Integer>();
			byte[] arr = new byte[14];
			
			try {
				pool.read(addr, arr);
			} catch (IOException e) {
				System.err.println("IOException occurred while reading node.");
			}
			
			// read City record handles
			for (byte i = 0; i < arr[1]; i++) {
				handles.add(getIntegerFromByteArray(arr, 2 + (i * 4)));
			}
		}
	}

	/* parameters */
	private final int MAX_BUCKET_SIZE = 3;
	private final int EMPTY_LEAF = -1;
	private final byte INTERNAL = 1;
	private final byte LEAF = 2;

	/* Private members */
	private Integer root;
	private int xMin, xMax, yMin, yMax;
	private boolean searchFound = false;
	private MemManager manager;
	private BufferPool pool;

	private boolean merge = false;
	private Integer mergedNode = -1;

	/**
	 * Constructor
	 * 
	 * @param xMin
	 *            Low x boundary
	 * @param xMax
	 *            High x boundary
	 * @param yMin
	 *            Low y boundary
	 * @param yMax
	 *            High y boundary
	 */
	public PRQuadFile(int xMin, int xMax, int yMin, int yMax, MemManager m,
			BufferPool p) {
		this.xMin = xMin;
		this.xMax = xMax;
		this.yMin = yMin;
		this.yMax = yMax;

		manager = m;
		pool = p;

		if (xMin >= xMax || yMin >= yMax)
			throw new IndexOutOfBoundsException();
		clear();
	}

	/**
	 * Inserts a City at given x, y coordinates and returns the true if insert
	 * was successful
	 * 
	 */
	public boolean insert(City c) {
		Coordinates TL = new Coordinates(xMin, yMin);
		Coordinates BR = new Coordinates(xMax, yMax);
		if (root == null) {
			prQuadLeaf leaf = new prQuadLeaf(root = manager.allocate(14));
			leaf.saveNode();
		}

		Integer result = insertHelper(root, c, TL, BR);
		if (result != -1) {
			root = result;
			getNode(root).saveNode();
		}
		
		return (result != -1);
	}

	/**
	 * Attempt to remove a city from the quadtree
	 * 
	 * @param coord
	 *            x, y coordinates of the target city to remove
	 * @return the City at given coordinates if it exists, null otherwise
	 */
	public City remove(Coordinates coord) {
		Coordinates TL = new Coordinates(xMin, yMin);
		Coordinates BR = new Coordinates(xMax, yMax);
		City val = removeHelper(coord, root, TL, BR);
		
		if (merge)
		{
			merge = false;
			root = mergedNode;
		}
		
		if (getNode(root).size() == 0) {
			manager.deallocate(root);
			root = -1;
		}
		
		return val;
	}

	/**
	 * Traverse through and print the nodes of the tree.
	 */
	public void debug() {
		if (root == null || root == -1) {
			System.out.print("*");
		} else {
			getNode(root).printData();
			System.out.println();
		}

		System.out.flush();
	}

	public void clear() {
		root = null;
	}

	/**
	 * Helper method to insert a City given its x, y coordinates
	 * 
	 * @param c
	 *            City with name handle, x, and y coordinates
	 * @param tree
	 *            root of tree to insert to
	 * @return true if insert was successful, false otherwise
	 */
	private Integer insertHelper(Integer tree, City c, Coordinates TL,
			Coordinates BR) {
		Integer result = -1;
		if (tree == -1) { // empty leaf
			result = manager.allocate(14);
			prQuadLeaf leaf = new prQuadLeaf(result);
			leaf.saveNode();
			Integer cityHandle = manager.allocate(12);
			leaf.insertCity(cityHandle, c);
			leaf.saveNode();
		} else if (getNode(tree).isLeaf()) { // is non-empty leaf
			prQuadLeaf t = (prQuadLeaf) getNode(tree);
			t.readElements();
			
			if (t.size() < MAX_BUCKET_SIZE) {
				for (Integer handle: t.handles) {
					if (getCity(handle).getCoordinates().equals(c.getCoordinates())) {
						return -1;
					}
				}
				
				Integer cityHandle = manager.allocate(12);
				t.insertCity(cityHandle, c);
				t.saveNode();
				result = tree;
			} else {
				result = split(t, TL, BR);
				insertHelper(result, c, TL, BR);
			}
		} else { // internal node
			prQuadInternal t = (prQuadInternal) getNode(tree);

			switch (chooseQuadrant(c.getCoordinates(), TL, BR)) {
			case NW:
				if (t.getNW() == EMPTY_LEAF) {
					prQuadLeaf leaf = new prQuadLeaf(manager.allocate(14));
					leaf.saveNode();
					t.setNW(leaf.addr);
					t.saveNode();
				}
				result = insertHelper(
						t.getNW(),
						c,
						TL,
						new Coordinates(TL.getXCoord()
								+ (BR.getXCoord() - TL.getXCoord()) / 2, TL
								.getYCoord()
								+ (BR.getYCoord() - TL.getYCoord()) / 2));
				t.setNW(result);
				break;
			case SW:
				if (t.getSW() == EMPTY_LEAF) {
					prQuadLeaf leaf = new prQuadLeaf(manager.allocate(14));
					leaf.saveNode();
					t.setSW(leaf.addr);
					t.saveNode();
				}

				result = insertHelper(
						t.getSW(),
						c,
						new Coordinates(TL.getXCoord(), TL.getYCoord()
								+ (BR.getYCoord() - TL.getYCoord()) / 2),
						new Coordinates(TL.getXCoord()
								+ (BR.getXCoord() - TL.getXCoord()) / 2, BR
								.getYCoord()));
				t.setSW(result);
				break;
			case NE:
				if (t.getNE() == EMPTY_LEAF) {
					prQuadLeaf leaf = new prQuadLeaf(manager.allocate(14));
					leaf.saveNode();
					t.setNE(leaf.addr);
					t.saveNode();
				}

				result = insertHelper(
						t.getNE(),
						c,
						new Coordinates(TL.getXCoord()
								+ (BR.getXCoord() - TL.getXCoord()) / 2, TL
								.getYCoord()),
						new Coordinates(BR.getXCoord(), TL.getYCoord()
								+ (BR.getYCoord() - TL.getYCoord()) / 2));
				t.setNE(result);
				break;
			case SE:
				if (t.getSE() == EMPTY_LEAF) {
					prQuadLeaf leaf = new prQuadLeaf(manager.allocate(14));
					leaf.saveNode();
					t.setSE(leaf.addr);
					t.saveNode();
				}

				result = insertHelper(
						t.getSE(),
						c,
						new Coordinates(TL.getXCoord()
								+ (BR.getXCoord() - TL.getXCoord()) / 2, TL
								.getYCoord()
								+ (BR.getYCoord() - TL.getYCoord()) / 2), BR);
				t.setSE(result);
			}
			t.saveNode();
			result = t.addr;
		}
		
		return result;
	}

	/**
	 * Split a leaf node
	 * 
	 * @param target
	 */
	private Integer split(prQuadLeaf target, Coordinates TL, Coordinates BR) {
		// deallocate leaf node
		manager.deallocate(target.addr);
		// allocate new internal node to take its place
		prQuadInternal splitNode = new prQuadInternal(manager.allocate(17));
		splitNode.saveNode();
		
		for (Integer handle : target.handles) {
			splitNode.addr = insertHelper(splitNode.addr, getCity(handle), TL,
					BR);
			manager.deallocate(handle);
		}

		return splitNode.addr;
	}
	
	/**
	 * Helper method to remove a City given its x, y coordinates
	 * 
	 * @param coord
	 *            Target x, y coordinates of expected city position
	 * @param tree
	 *            Node to search in
	 * @param tL
	 *            TL of region to search for
	 * @param bR
	 *            BR of region to search for
	 * @return
	 */
	private City removeHelper(Coordinates coord, Integer tree, Coordinates TL,
			Coordinates BR) {
		if (tree == -1) {
			return null;
		} else if (getNode(tree).isLeaf()) { // is a leaf
			prQuadLeaf leaf = new prQuadLeaf(tree);
			leaf.readElements();
			
			Iterator<Integer> iter = leaf.handles.iterator();

			while (iter.hasNext()) {
				Integer handle = iter.next();
				City val = getCity(handle);
				if (val.getCoordinates().equals(coord)) {
					iter.remove();
					// deallocate city within file
					manager.deallocate(handle);
					leaf.saveNode();
					return val;
				}
			}

			return null;
		} else {
			prQuadInternal internal = new prQuadInternal(tree);
			internal.readElements();
			Integer next = null;
			Coordinates nextTL = null;
			Coordinates nextBR = null;
			Quadrant quad = chooseQuadrant(coord, TL, BR);
			
			// set internal node to remove from
			switch (quad) {
			case NW:
				next = internal.getNW();
				nextTL = TL;
				nextBR = new Coordinates(TL.getXCoord()
						+ (BR.getXCoord() - TL.getXCoord()) / 2, TL.getYCoord()
						+ (BR.getYCoord() - TL.getYCoord()) / 2);
				break;
			case SW:
				next = internal.getSW();
				nextTL = new Coordinates(TL.getXCoord(), TL.getYCoord()
						+ (BR.getYCoord() - TL.getYCoord()) / 2);
				nextBR = new Coordinates(TL.getXCoord()
						+ (BR.getXCoord() - TL.getXCoord()) / 2, BR.getYCoord());
				break;
			case NE:
				next = internal.getNE();
				nextTL = new Coordinates(TL.getXCoord()
						+ (BR.getXCoord() - TL.getXCoord()) / 2, TL.getYCoord());
				nextBR = new Coordinates(BR.getXCoord(), TL.getYCoord()
						+ (BR.getYCoord() - TL.getYCoord()) / 2);
				break;
			case SE:
				next = internal.getSE();
				nextTL = new Coordinates(TL.getXCoord()
						+ (BR.getXCoord() - TL.getXCoord()) / 2, TL.getYCoord()
						+ (BR.getYCoord() - TL.getYCoord()) / 2);
				nextBR = BR;
			}
			// remove from internal node
			City val = removeHelper(coord, next, nextTL, nextBR);
			
			// child was merged, update child handle
			if (merge) {
				switch (quad) {
				case NW:
					internal.setNW(mergedNode);
					break;
				case NE:
					internal.setNE(mergedNode);
					break;
				case SW:
					internal.setSW(mergedNode);
					break;
				case SE:
					internal.setSE(mergedNode);
				}
				
				merge = false;
				mergedNode = -1;
				internal.saveNode();
			}
			
			// check if this internal node needs to be merged 
			if (val != null && internal.size() <= MAX_BUCKET_SIZE) {
				mergedNode = merge(internal.addr);
			} else if (val != null){
				switch (quad) {
				case NW:
					if (getNode(internal.getNW()).size() == 0) {
						// deallocate now-empty leaf node
						manager.deallocate(internal.getNW());
						internal.setNW(-1);
					}
					break;
				case NE:
					if (getNode(internal.getNE()).size() == 0) {
						// deallocate now-empty leaf node
						manager.deallocate(internal.getNE());
						internal.setNE(-1);
					}
					break;
				case SW:
					if (getNode(internal.getSW()).size() == 0) {
						// deallocate now-empty leaf node
						manager.deallocate(internal.getSW());
						internal.setSW(-1);
					}
					break;
				case SE:
					if (getNode(internal.getSE()).size() == 0) {
						// deallocate now-empty leaf node
						manager.deallocate(internal.getSE());
						internal.setSE(-1);
					}
				}
				
				internal.saveNode();
			}
			
			return val;
		}
	}

	private Integer merge(Integer mergeTarget) {
		merge = true;
		prQuadInternal target = new prQuadInternal(mergeTarget);
		target.readElements();
		
		prQuadLeaf leaf = new prQuadLeaf(manager.allocate(14));
		
		if (target.getNW() != -1) {
			prQuadLeaf child = new prQuadLeaf(target.getNW());
			child.readElements();

			leaf.handles.addAll(child.handles);
			// deallocate target internal node's child node
			manager.deallocate(child.addr);
		}
		
		if (target.getNE() != -1) {
			prQuadLeaf child = new prQuadLeaf(target.getNE());
			child.readElements();
			
			leaf.handles.addAll(child.handles);
			// deallocate target internal node's child node
			manager.deallocate(child.addr);
		}
		
		if (target.getSW() != -1) {
			prQuadLeaf child = new prQuadLeaf(target.getSW());
			child.readElements();
			
			leaf.handles.addAll(child.handles);
			// deallocate target internal node's child node
			manager.deallocate(child.addr);
		}
		
		if (target.getSE() != -1) {
			prQuadLeaf child = new prQuadLeaf(target.getSE());
			child.readElements();
			
			leaf.handles.addAll(child.handles);
			// deallocate target internal node's child node
			manager.deallocate(child.addr);
		}
		
		leaf.saveNode();
		// deallocate target internal node
		manager.deallocate(mergeTarget);
		return leaf.addr;
	}

	private Quadrant chooseQuadrant(Coordinates coord, Coordinates TL, Coordinates BR) {
		Coordinates midPoint = new Coordinates(TL.getXCoord()
				+ (BR.getXCoord() - TL.getXCoord()) / 2, TL.getYCoord()
				+ (BR.getYCoord() - TL.getYCoord()) / 2);
		if (coord.getXCoord() < midPoint.getXCoord()) {
			if (coord.getYCoord() < midPoint.getYCoord())
				return Quadrant.NW;
			else
				return Quadrant.SW;
		} else {
			if (coord.getYCoord() < midPoint.getYCoord())
				return Quadrant.NE;
			else
				return Quadrant.SE;
		}
	}

	private City getCity(Integer handle) {
		byte[] arr = new byte[12];
		try {
			pool.read(handle, arr);
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		Coordinates coord = new Coordinates(getIntegerFromByteArray(arr, 0),
				getIntegerFromByteArray(arr, 4));
		City val = new City(getIntegerFromByteArray(arr, 8), coord);

		return val;
	}

	private prQuadNode getNode(Integer handle) {
		byte[] arr = new byte[17];
		try {
			pool.read(handle, arr);
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}

		if (arr[0] == INTERNAL) {
			prQuadInternal internal = new prQuadInternal(handle);
			internal.readElements();
			
			return internal;
		}
		else if (arr[0] == LEAF) {
			prQuadLeaf leaf = new prQuadLeaf(handle);
			leaf.readElements();
			
			return leaf;
		}
		else {
			System.err.println("No node found at given address. " + arr[0]);
			return null;
		}
	}

	private void insertToByteArray(Integer handle, int offset, byte[] arr) {
		Integer temp = new Integer(handle);

		for (int i = 3; i >= 0; i--) {
			arr[offset + (3 - i)] = (byte) (0xFF & (temp >> (8 * i)));
		}
	}

	private Integer getIntegerFromByteArray(byte[] array, int offset) {
		int val = 0;

		for (int i = 0; i < 4; i++) {
			val = val << 8;
			val = val | (0x00FF & array[offset + i]);		
		}
		return val;
	}

	private String readString(Integer handle) {
		byte[] buff = new byte[256];
		int size = 0;
		try {
			size = pool.read(handle, buff);
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		return new String(buff, 0, size);
	}
	
	public int search(int x, int y, int radius) {
		searchFound = false;
		Coordinates coord = new Coordinates(x, y);
		Coordinates TL = new Coordinates(xMin, yMin);
		Coordinates BR = new Coordinates(xMax, yMax);
		int result = searchHelper(coord, radius, TL, BR, root);
		if (!searchFound) {
			System.out.println("No such record found.");
		}
		return result;
	}

	/**
	 * Helper method to search a given area
	 */
	private int searchHelper(Coordinates coord, int radius, Coordinates TL, Coordinates BR, Integer sRoot) {

		boolean overlaps = sRoot != -1 && boundCheck(coord, radius, TL, BR);

		if (!overlaps)
			return 0;

		// overlapping leaf
		if (sRoot != -1){
			prQuadNode rt = getNode(sRoot);
			if (rt.isLeaf()) {
				if (sRoot != EMPTY_LEAF) {
					for (int i = 0; i < ((prQuadLeaf) rt).handles.size(); i++) {
						if (radiusCheck(getCity(((prQuadLeaf) rt).handles.get(i)).getCoordinates(),	coord, radius)) {
							City result = getCity(((prQuadLeaf)rt).handles.get(i));
							System.out.println(result + "," + readString(result.handle())); 
							searchFound = true;
						}
					}
				}
	
				return 1;
			} else {	// search internal node's children
				Coordinates TM = new Coordinates(TL.getXCoord() + (BR.getXCoord() - TL.getXCoord())/2, TL.getYCoord());
				Coordinates LM = new Coordinates(TL.getXCoord(), TL.getYCoord() + (BR.getYCoord() - TL.getYCoord())/2);
				Coordinates M = new Coordinates(TM.getXCoord(), LM.getYCoord());
				Coordinates RM = new Coordinates(BR.getXCoord(), LM.getYCoord());
				Coordinates BM = new Coordinates(TM.getXCoord(), BR.getYCoord());
				
				return searchHelper(coord, radius, TL, M, ((prQuadInternal)rt).getNW()) +
	                   searchHelper(coord, radius, LM, BM, ((prQuadInternal)rt).getSW()) +
	                   searchHelper(coord, radius, TM, RM, ((prQuadInternal)rt).getNE()) +
	                   searchHelper(coord, radius, M, BR, ((prQuadInternal)rt).getSE()) + 1;
			}
		}
		return 0;
	}

	private boolean boundCheck(Coordinates coord, int radius, Coordinates tL,
			Coordinates bR) {
		Coordinates top = new Coordinates(coord.getXCoord(), tL.getYCoord());
		Coordinates bottom = new Coordinates(coord.getXCoord(), bR.getYCoord());
		Coordinates right = new Coordinates(bR.getXCoord(), coord.getYCoord());
		Coordinates left = new Coordinates(tL.getYCoord(), coord.getYCoord());
		
		return coord.getXCoord() >= tL.getXCoord() && coord.getXCoord() < bR.getXCoord() && radiusCheck(coord, top, radius)
			|| coord.getXCoord() >= tL.getXCoord() && coord.getXCoord() < bR.getXCoord() && radiusCheck(coord, bottom, radius)
			|| coord.getYCoord() >= tL.getYCoord() && coord.getYCoord() < bR.getYCoord() && radiusCheck(coord, right, radius)
			|| coord.getYCoord() >= tL.getYCoord() && coord.getYCoord() < bR.getYCoord() && radiusCheck(coord, left, radius)
			|| coord.getXCoord() >= tL.getXCoord() && coord.getXCoord() < bR.getXCoord()
				&& coord.getYCoord() >= tL.getYCoord() && coord.getYCoord() < bR.getYCoord();
	}

	/**
	 * Helper method to check if two points are within a certain distance.
	 * 
	 * @param a
	 *            point a
	 * @param b
	 *            point b
	 * @param radius
	 *            maximum distance between a and b
	 * @return true if a and b are within radius
	 */
	private boolean radiusCheck(Coordinates a, Coordinates b, int radius) {
		int xLen = java.lang.Math.abs(a.getXCoord() - b.getXCoord());
		int yLen = java.lang.Math.abs(a.getYCoord() - b.getYCoord());

		return ((int) java.lang.Math.sqrt(xLen * xLen + yLen * yLen) <= radius);
	}
}
